package com.wxit.algorithm.leetcode;

/**
 * 删除链表的倒数第N个节点
 */
public class E03LeetCode19 {

    /**
     * 方法二 快慢指针法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //定义一个哨兵节点
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2 = s;
        //p2先走 n+1 步
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        //删除倒数第n个节点
        p1.next = p1.next.next;
        return s.next;
    }


    /**
     * 方法1 递归解法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd02(ListNode head, int n) {
        //引入哨兵节点
        ListNode s = new ListNode(-1, head);
        recursion(s, n);
        return s.next;
    }

    private int recursion(ListNode p, int n) {
        if (p == null) {
            return 0;
        }
        //下一个节点的倒数位置
        int nth = recursion(p.next, n);
        System.out.println(p.val + " " + nth);
        if (nth == n) {
            p.next = p.next.next;
        }
        return nth + 1;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 3, 4, 5);
        System.out.println(head);
        System.out.println(new E03LeetCode19().removeNthFromEnd(head, 5));
    }
}
